package Leetcode;

/**
 * 反转链表
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 */
public class test206 {


    /**
     * 遍历链表，利用头插将其放入新的链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode dummyHead=new ListNode();
        //遍历链表的同时建立新的链表
        while (head!=null){
            ListNode node=new ListNode(head.val);
            node.next=dummyHead.next;
            dummyHead.next=node;
             head=head.next;
        }
        return dummyHead.next;
    }

    /**
     * 原地反转链表
     * @param head
     * @return
     */
    public ListNode reverseList1(ListNode head) {
          if(head==null||head.next==null){
              return head;
          }
          ListNode prev=null;
          ListNode fir=head;
          while(fir!=null){
              //此时先暂存一下下一个要处理的节点
              ListNode sec=fir.next;
              //让正在处理的节点往回指引
              fir.next=prev;
              //prev和fir往下接着走
              prev=fir;
              fir=sec;
          }
          //此时链表遍历结束，恰好prev就是头节点
          return prev;
    }


    /**
     * 使用递归思路
     * @param head
     * @return
     */
    public ListNode reverseList2(ListNode head){
        if (head==null||head.next==null){
            return head;
        }
        //先暂存第二个节点的地址
        ListNode node=head.next;
        //从第二个节点开始的子链表交给子函数处理
        ListNode newHead=reverseList(head.next);
        //拼接
        node.next=head;
        head.next=null;
        return newHead;
    }

}
